package com.fireway;

import java.util.NoSuchElementException;

/**
 * 有序单链表
 * 2018年 05月 05日 星期六
 *
 * @author fireway
 */
public class SortedLinkedList<E> {
    private Entry<E> mHeader;  // 表头

    private int mSize = 0;

    public SortedLinkedList() {
        mHeader = null;
    }

    public void add(E item) {
        Entry<E> newEntry = new Entry<E>(item);
        Entry<E> current = mHeader;
        Entry<E> previous = null;

        while (current != null && (compare(item, current.mElement) > 0)) {
            previous = current;
            current = current.mNext;
        }

        if (null == previous) {
            mHeader = newEntry;
        } else {
            previous.mNext = newEntry;
        }
        mSize++;

        newEntry.mNext = current;
    }

    private int compare(Object e1, Object e2) {
        Comparable c1 = (Comparable)e1;
        Comparable c2 = (Comparable)e2;
        int result = c1.compareTo(c2);
        return result;
    }

    public E remove() {
        if (empty()) {
            throw new NoSuchElementException();
        } else {
            Entry<E> tmp = mHeader;
            E result = tmp.mElement;
            mHeader = tmp.mNext;
            mSize--;
            return result;
        }
    }

    public boolean empty() {
        // 当mHeader的值为null，就表明链表中没有数据项。
        // 如果有，mHeader应该存有对第一个链接点
        // 的引用值。
        return null == mHeader;
    }

    /**
     * Returns the index of the first occurrence of the specified element
     * in this list, or -1 if this list does not contain the element.
     *
     */
    public int indexOf(Object o) {
        int index = 0;
        for (Entry<E> e = mHeader; e != null ; e = e.mNext) {
            if (isEqual(o, e.mElement)) {
                return index;
            }
            index++;
        }

        return -1;
    }

    private boolean isEqual(Object o, E element) {
        if (null == o) {
            return element == null;
        } else {
            return o.equals(element);
        }
    }

    /**
     * Returns the element at the specified position in this list.
     * @param index index of the element to return
     * @return the element at the specified position in this list
     */
    public E get(int index) {
        if (index < 0 || index >= mSize) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + mSize);
        }

        Entry<E> e = mHeader;
        for (int i = 0; i < index; i++) {
            e = e.mNext;
        }

        return e.mElement;
    }

    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer();

        sb.append("[");
        for (int i = 0; i < mSize; i++) {
            E e = get(i);
            sb.append(e);
            if (i != mSize - 1) {
                sb.append(", ");
            }
        }
        sb.append("]");

        return sb.toString();
    }

    private static class Entry<E> {
        E mElement;
        Entry<E> mNext;

        public Entry(E element) {
            mElement = element;
        }
    }
}
